package ca.tatham.scheduler;

public abstract class PrioritizedQueue<E extends Prioritizable> {

	private final Node<E> m_root;

	public PrioritizedQueue() {
		m_root = new Node<E>(null, null);
	}

	public E peek() {
		if (m_root.next == null) {
			return null;
		}
		return m_root.next.element;
	}

	public E pop() {
		if (m_root.next == null) {
			return null;
		}
		E task = m_root.next.element;
		m_root.next = m_root.next.next;
		return task;
	}

	protected Node<E> getRoot() {
		return m_root;
	}

	public void add(E newE) {
		Node<E> n = m_root;
		while (n.next != null) {
			int compare = compare(n.next.element, newE);
			if (compare > 0) {
				break;
			}
			n = n.next;
		}
		n.next = new Node<E>(newE, n.next);
	}

	protected abstract int compare(E e1, E e2);

	protected E remove(E element) {
		Node<E> n = getRoot();
		while (n.next != null) {
			if (n.next.element == element) {
				n.next = n.next.next;
				return element;
			}
			n = n.next;
		}
		return null;
	}

	protected static class Node<E extends Prioritizable> {
		final E element;
		Node<E> next;

		Node(E e, Node<E> n) {
			next = n;
			element = e;
		}
	}

}